The use of remote computing services, such as remote program execution and remote data storage, has greatly increased in recent years. Customers may reduce expenses and overhead by purchasing these services from a computing resource service provider. Customers of the computing resource service provider can communicate with computing systems, services and virtual machine instances which are widely distributed over many geographically dispersed networks. Customers, for instance, may communicate with computers of other customers to access and/or provide data while using services of a computing resource service provider. In many instances, customers configure and operate remote networks using hardware managed by computing resource service providers, thereby reducing infrastructure costs and achieving other advantages. Networks often span multiple geographic boundaries connecting with other networks and connection errors may occur at various points a long a communication path. With such configurations of networks and computing resources, ensuring connectivity between resources can be challenging, especially as the size and complexity of such networks grow.